/**
 *  给定初始单词，结束单词，以及单词列表
 *	要求找到最短的路径从初始到结束。相邻单词有且只有一个字母不同
 *	双向广搜必须成批扩展，否则答案有可能差一点
 *  如果边权不一样，可能无法双向广搜
 */
#include <bits/stdc++.h>
using namespace std;

class Solution {
using vi = vector<int>;
map<string, int> Map;	
vector<vi> G;
int N;
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        N = wordList.size() + 1;
		Map[beginWord] = 1;
		for(int i=0;i<wordList.size();++i){
			const auto & si = wordList[i];
			if(si == beginWord) continue;
			Map[si] = i + 2;
		}     

        G.assign(N + 1, {});
		for(int i=0;i<wordList.size();++i){
			if(isOK(beginWord, wordList[i])){
                G[1].emplace_back(i + 2);
				G[i + 2].emplace_back(1); 
			}
			for(int j=i+1;j<wordList.size();++j){
                if(isOK(wordList[i], wordList[j])){
					G[i + 2].emplace_back(j + 2);
					G[j + 2].emplace_back(i + 2);
				}
			}
		}

		auto it = Map.find(endWord);
		if(it == Map.end()) return 0;
		auto dst = it->second;

        vi Fa(N + 1, -1);
		vi Fb(N + 1, -1);
		queue<int> qa, qb;
		qa.push(1); 
		qb.push(dst);
		Fa[1] = 0; Fb[dst] = 0;
		while(not qa.empty() and not qb.empty()){
			auto sz = qa.size();
			while(sz--){
				auto h = qa.front(); qa.pop();
				// if(Fb[h] != -1) return Fa[h] + Fb[h] + 1;
				for(auto v : G[h]){
					if(Fa[v] != -1) continue;
					if(Fb[v] != -1) return Fa[h] + 2 + Fb[v];
					Fa[v] = Fa[h] + 1;
					qa.push(v);
				}
			}
			sz = qb.size();
			while(sz--){
				auto h = qb.front(); qb.pop();
				// if(Fa[h] != -1) Fa[h] + Fb[h] + 1;
				for(auto v : G[h]){
					if(Fb[v] != -1) continue;
					if(Fa[v] != -1) return Fb[h] + 2 + Fa[v];
					Fb[v] = Fb[h] + 1;
					qb.push(v);
				}
			}
		}
		
		return 0;
    }

	bool isOK(const string & s, const string & t){
		int c = 0;
		for(int i=0;i<s.length();++i){
            if(s[i] != t[i]){
				if((c += 1) > 1) return false;
			}
		}
		return 1 == c;
	}
};